import java.util.Arrays;

/**
 * 932. 漂亮数组
 * https://leetcode-cn.com/problems/beautiful-array/
 */
public class Solutions_932 {
    public static void main(String[] args) {
//        int N = 4;  // output: {1, 3, 2, 4} or {2, 1, 4, 3}
//        int N = 5;  // output: {1, 5, 3, 2, 4} or {3, 1, 2, 5, 4}
        int N = 6;  // output: {1, 5, 3, 2, 6, 4}

        int[] result = beautifulArray(N);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解题思路：分治法
     * 长度为 3：{1, 3, 2}
     * 长度为 4：{1, 3, 2, 4}
     * 长度为 5：{1, 5, 3, 2, 4}
     * 长度为 6：{1, 5, 3, 2, 6, 4}
     *
     * 左侧部分，奇数计算：n * 2 - 1，右侧部分，偶数计算：n * 2
     * 当 N = 5 时，res 数组构造过程：
     * 自底向上模拟：
     * {1}, {1}, {1}, {1}, {1}
     * {1, 2}, {1}, {1, 2}
     * {1, 3, 2}, {1, 2}
     * {1, 5, 3, 2, 4}
     */
    public static int[] beautifulArray(int N) {
        if (N == 1) {
            return new int[]{1};
        }
        int[] res = new int[N];
        // 奇数部分
        int[] odd = beautifulArray((N + 1) / 2);
        // 偶数部分
        int[] even = beautifulArray(N / 2);

        for (int i = 0; i < odd.length; i++) {
            res[i] = odd[i] * 2 - 1;
        }
        for (int i = 0; i < even.length; i++) {
            res[i + odd.length] = even[i] * 2;
        }
        return res;
    }
}
